package arithmetic.changba;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * 二叉树的序列化，和反序列化 用列表模拟
 */
public class BinTreeSerilize {

    // 定义一个二叉树数据结构
    class BinTreeNode {

        Integer value;
        BinTreeNode left;
        BinTreeNode right;
    }

    public static void main(String[] args) {
        new BinTreeSerilize().init();
    }

    public void init() {
        List test = Arrays.asList(30, 10, 50, '#', '#', '#', 20, 45, '#', '#', 35, '#', '#');
        //30 10 50 # # # 20 45 # # 35 # #
        BinTreeNode newNode = listToNode(test);
        System.out.println(newNode);

//		再重新转化为list
        List newlist = treetoList(newNode, new ArrayList());
        List newlist2 = treeTolist2(newNode, new ArrayList());
        for (Object l : newlist2) {
            System.out.print(l);
            System.out.print(',');
        }
    }

    /**
     * 先序遍历,把二叉树序列化为列表
     */
    public List treetoList(BinTreeNode node, List list) {
        if (null != node) {
            list.add(node.value);
            treetoList(node.left, list);
            treetoList(node.right, list);
        } else {
            list.add('#');
        }
        return list;
    }

    /**
     * 二叉树的先序遍历，非递归实现 思路： 输入一个节点，判断其是否有值，有则将当前节点 进栈， 在判断其左节点是否为空，
     */
    public List treeTolist2(BinTreeNode node, List list) {
        if (null == node) {
            return list;
        }
        Stack stack = new Stack();
        BinTreeNode p = node;
        while (null != p || !stack.empty()) {
            list.add(p.value);
            stack.push(p);
            p = p.left;
            // 1.左节点不为空时就循环打印左节点 2.左节点为空且栈内有值，则可以进入右节点
            while (null == p && !stack.empty()) {
                if (p == null) {
                    list.add("#");
                }
                // 根节点出栈,循环找根节点，一直到找到有值的右节点。
                p = (BinTreeNode) stack.pop();
                p = p.right;
            }
        }
        return list;
    }

    int index = 0;

    /**
     * 更具list生成二叉树，需要借助一个外在变量记录当前序列化的位置。
     */
    public BinTreeNode listToNode(List list) {
        Object value = list.get(index);
        index++;
        BinTreeNode node = null;
        if (value instanceof Integer) {
            node = new BinTreeNode();
            node.value = (Integer) value;
            node.left = listToNode(list);
            node.right = listToNode(list);
        }
        return node;
    }


}
